Out of-order processors typically comprise a branch predictor which predicts which direction the program flow will take in the case of instructions known to cause possible flow changes, such as a branch instructions. Branch prediction is useful as it enables instructions to be speculatively executed by the processor before the outcome of the branch instruction is known.
However, indirect branches (e.g. branches based on a variable rather than a constant value) are difficult to predict as the branch predictor must predict both whether the branch is taken and where the target will be. Accordingly, many branch predictors are unable to accurately predict indirect branches.
One solution to this has been to improve the prediction algorithm used by the branch predictor. However, this is often quite difficult and time intensive.
Another solution has been to implement a compiler that is configured to remove code related to any switch-like structure thus removing the need for an indirect branch. However, it is difficult to recognize situations in which the code can be removed.
The embodiments described below are not limited to implementations which solve any or all of the disadvantages of known out-of-order processors.